#define DEBUG
using System;
using System.Collections;
using System.Diagnostics;
using System.Globalization;
using System.Text;

namespace Com.FirstSolver.Splash;

[Serializable]
public class BigInteger
{
	private static readonly int[][] primeLists;

	private static readonly int[] primeProducts;

	private const long IMASK = 4294967295L;

	private static readonly ulong UIMASK;

	private static readonly int[] ZeroMagnitude;

	private static readonly byte[] ZeroEncoding;

	public static readonly BigInteger Zero;

	public static readonly BigInteger One;

	public static readonly BigInteger Two;

	public static readonly BigInteger Three;

	public static readonly BigInteger Ten;

	private static readonly int chunk2;

	private static readonly BigInteger radix2;

	private static readonly BigInteger radix2E;

	private static readonly int chunk10;

	private static readonly BigInteger radix10;

	private static readonly BigInteger radix10E;

	private static readonly int chunk16;

	private static readonly BigInteger radix16;

	private static readonly BigInteger radix16E;

	private static readonly Random RandomSource;

	private const int BitsPerByte = 8;

	private const int BitsPerInt = 32;

	private const int BytesPerInt = 4;

	private int sign;

	private int[] magnitude;

	private int nBits = -1;

	private int nBitLength = -1;

	private long mQuote = -1L;

	private static readonly byte[] rndMask;

	private static readonly byte[] bitCounts;

	public int BitCount
	{
		get
		{
			if (nBits == -1)
			{
				if (sign < 0)
				{
					nBits = Not().BitCount;
				}
				else
				{
					int sum = 0;
					for (int i = 0; i < magnitude.Length; i++)
					{
						sum += bitCounts[(byte)magnitude[i]];
						sum += bitCounts[(byte)(magnitude[i] >> 8)];
						sum += bitCounts[(byte)(magnitude[i] >> 16)];
						sum += bitCounts[(byte)(magnitude[i] >> 24)];
					}
					nBits = sum;
				}
			}
			return nBits;
		}
	}

	public int BitLength
	{
		get
		{
			if (nBitLength == -1)
			{
				nBitLength = ((sign != 0) ? calcBitLength(0, magnitude) : 0);
			}
			return nBitLength;
		}
	}

	public int IntValue => (sign != 0) ? ((sign > 0) ? magnitude[magnitude.Length - 1] : (-magnitude[magnitude.Length - 1])) : 0;

	public long LongValue
	{
		get
		{
			if (sign == 0)
			{
				return 0L;
			}
			long v = ((magnitude.Length <= 1) ? (magnitude[magnitude.Length - 1] & 0xFFFFFFFFu) : (((long)magnitude[magnitude.Length - 2] << 32) | (magnitude[magnitude.Length - 1] & 0xFFFFFFFFu)));
			return (sign < 0) ? (-v) : v;
		}
	}

	public int SignValue => sign;

	static BigInteger()
	{
		primeLists = new int[52][]
		{
			new int[8] { 3, 5, 7, 11, 13, 17, 19, 23 },
			new int[5] { 29, 31, 37, 41, 43 },
			new int[5] { 47, 53, 59, 61, 67 },
			new int[4] { 71, 73, 79, 83 },
			new int[4] { 89, 97, 101, 103 },
			new int[4] { 107, 109, 113, 127 },
			new int[4] { 131, 137, 139, 149 },
			new int[4] { 151, 157, 163, 167 },
			new int[4] { 173, 179, 181, 191 },
			new int[4] { 193, 197, 199, 211 },
			new int[3] { 223, 227, 229 },
			new int[3] { 233, 239, 241 },
			new int[3] { 251, 257, 263 },
			new int[3] { 269, 271, 277 },
			new int[3] { 281, 283, 293 },
			new int[3] { 307, 311, 313 },
			new int[3] { 317, 331, 337 },
			new int[3] { 347, 349, 353 },
			new int[3] { 359, 367, 373 },
			new int[3] { 379, 383, 389 },
			new int[3] { 397, 401, 409 },
			new int[3] { 419, 421, 431 },
			new int[3] { 433, 439, 443 },
			new int[3] { 449, 457, 461 },
			new int[3] { 463, 467, 479 },
			new int[3] { 487, 491, 499 },
			new int[3] { 503, 509, 521 },
			new int[3] { 523, 541, 547 },
			new int[3] { 557, 563, 569 },
			new int[3] { 571, 577, 587 },
			new int[3] { 593, 599, 601 },
			new int[3] { 607, 613, 617 },
			new int[3] { 619, 631, 641 },
			new int[3] { 643, 647, 653 },
			new int[3] { 659, 661, 673 },
			new int[3] { 677, 683, 691 },
			new int[3] { 701, 709, 719 },
			new int[3] { 727, 733, 739 },
			new int[3] { 743, 751, 757 },
			new int[3] { 761, 769, 773 },
			new int[3] { 787, 797, 809 },
			new int[3] { 811, 821, 823 },
			new int[3] { 827, 829, 839 },
			new int[3] { 853, 857, 859 },
			new int[3] { 863, 877, 881 },
			new int[3] { 883, 887, 907 },
			new int[3] { 911, 919, 929 },
			new int[3] { 937, 941, 947 },
			new int[3] { 953, 967, 971 },
			new int[3] { 977, 983, 991 },
			new int[3] { 997, 1009, 1013 },
			new int[3] { 1019, 1021, 1031 }
		};
		UIMASK = 4294967295uL;
		ZeroMagnitude = new int[0];
		ZeroEncoding = new byte[0];
		Zero = new BigInteger(0, ZeroMagnitude, checkMag: false);
		One = createUValueOf(1uL);
		Two = createUValueOf(2uL);
		Three = createUValueOf(3uL);
		Ten = createUValueOf(10uL);
		chunk2 = 1;
		radix2 = ValueOf(2L);
		radix2E = radix2.Pow(chunk2);
		chunk10 = 19;
		radix10 = ValueOf(10L);
		radix10E = radix10.Pow(chunk10);
		chunk16 = 16;
		radix16 = ValueOf(16L);
		radix16E = radix16.Pow(chunk16);
		RandomSource = new Random();
		rndMask = new byte[8] { 255, 127, 63, 31, 15, 7, 3, 1 };
		bitCounts = new byte[256]
		{
			0, 1, 1, 2, 1, 2, 2, 3, 1, 2,
			2, 3, 2, 3, 3, 4, 1, 2, 2, 3,
			2, 3, 3, 4, 2, 3, 3, 4, 3, 4,
			4, 5, 1, 2, 2, 3, 2, 3, 3, 4,
			2, 3, 3, 4, 3, 4, 4, 5, 2, 3,
			3, 4, 3, 4, 4, 5, 3, 4, 4, 5,
			4, 5, 5, 6, 1, 2, 2, 3, 2, 3,
			3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
			2, 3, 3, 4, 3, 4, 4, 5, 3, 4,
			4, 5, 4, 5, 5, 6, 2, 3, 3, 4,
			3, 4, 4, 5, 3, 4, 4, 5, 4, 5,
			5, 6, 3, 4, 4, 5, 4, 5, 5, 6,
			4, 5, 5, 6, 5, 6, 6, 7, 1, 2,
			2, 3, 2, 3, 3, 4, 2, 3, 3, 4,
			3, 4, 4, 5, 2, 3, 3, 4, 3, 4,
			4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
			2, 3, 3, 4, 3, 4, 4, 5, 3, 4,
			4, 5, 4, 5, 5, 6, 3, 4, 4, 5,
			4, 5, 5, 6, 4, 5, 5, 6, 5, 6,
			6, 7, 2, 3, 3, 4, 3, 4, 4, 5,
			3, 4, 4, 5, 4, 5, 5, 6, 3, 4,
			4, 5, 4, 5, 5, 6, 4, 5, 5, 6,
			5, 6, 6, 7, 3, 4, 4, 5, 4, 5,
			5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
			4, 5, 5, 6, 5, 6, 6, 7, 5, 6,
			6, 7, 6, 7, 7, 8
		};
		primeProducts = new int[primeLists.Length];
		for (int i = 0; i < primeLists.Length; i++)
		{
			int[] primeList = primeLists[i];
			int product = 1;
			for (int j = 0; j < primeList.Length; j++)
			{
				product *= primeList[j];
			}
			primeProducts[i] = product;
		}
	}

	private static int GetByteLength(int nBits)
	{
		return (nBits + 8 - 1) / 8;
	}

	private BigInteger()
	{
	}

	private BigInteger(int signum, int[] mag, bool checkMag)
	{
		if (checkMag)
		{
			int i;
			for (i = 0; i < mag.Length && mag[i] == 0; i++)
			{
			}
			if (i == mag.Length)
			{
				magnitude = ZeroMagnitude;
				return;
			}
			sign = signum;
			if (i == 0)
			{
				magnitude = mag;
				return;
			}
			magnitude = new int[mag.Length - i];
			Array.Copy(mag, i, magnitude, 0, magnitude.Length);
		}
		else
		{
			sign = signum;
			magnitude = mag;
		}
	}

	public BigInteger(string value)
		: this(value, 10)
	{
	}

	public BigInteger(string str, int radix)
	{
		if (str.Length == 0)
		{
			throw new FormatException("Zero length BigInteger");
		}
		NumberStyles style;
		int chunk;
		BigInteger r;
		BigInteger rE;
		switch (radix)
		{
		case 2:
			style = NumberStyles.Integer;
			chunk = chunk2;
			r = radix2;
			rE = radix2E;
			break;
		case 10:
			style = NumberStyles.Integer;
			chunk = chunk10;
			r = radix10;
			rE = radix10E;
			break;
		case 16:
			style = NumberStyles.AllowHexSpecifier;
			chunk = chunk16;
			r = radix16;
			rE = radix16E;
			break;
		default:
			throw new FormatException("Only bases 2, 10, or 16 allowed");
		}
		int index = 0;
		sign = 1;
		if (str[0] == '-')
		{
			if (str.Length == 1)
			{
				throw new FormatException("Zero length BigInteger");
			}
			sign = -1;
			index = 1;
		}
		for (; index < str.Length && int.Parse(str[index].ToString(), style) == 0; index++)
		{
		}
		if (index >= str.Length)
		{
			sign = 0;
			magnitude = ZeroMagnitude;
			return;
		}
		BigInteger b = Zero;
		int next = index + chunk;
		if (next <= str.Length)
		{
			do
			{
				string s2 = str.Substring(index, chunk);
				ulong j = ulong.Parse(s2, style);
				BigInteger bi2 = createUValueOf(j);
				switch (radix)
				{
				case 2:
					if (j > 1)
					{
						throw new FormatException("Bad character in radix 2 string: " + s2);
					}
					b = b.ShiftLeft(1);
					break;
				case 16:
					b = b.ShiftLeft(64);
					break;
				default:
					b = b.Multiply(rE);
					break;
				}
				b = b.Add(bi2);
				index = next;
				next += chunk;
			}
			while (next <= str.Length);
		}
		if (index < str.Length)
		{
			string s = str.Substring(index);
			ulong i = ulong.Parse(s, style);
			BigInteger bi = createUValueOf(i);
			if (b.sign > 0)
			{
				switch (radix)
				{
				case 2:
					Debug.Assert(condition: false);
					break;
				case 16:
					b = b.ShiftLeft(s.Length << 2);
					break;
				default:
					b = b.Multiply(r.Pow(s.Length));
					break;
				}
				b = b.Add(bi);
			}
			else
			{
				b = bi;
			}
		}
		magnitude = b.magnitude;
	}

	public BigInteger(byte[] bytes)
		: this(bytes, 0, bytes.Length)
	{
	}

	public BigInteger(byte[] bytes, int offset, int length)
	{
		if (length == 0)
		{
			throw new FormatException("Zero length BigInteger");
		}
		if ((sbyte)bytes[offset] < 0)
		{
			sign = -1;
			int end = offset + length;
			int iBval;
			for (iBval = offset; iBval < end && (sbyte)bytes[iBval] == -1; iBval++)
			{
			}
			if (iBval >= end)
			{
				magnitude = One.magnitude;
				return;
			}
			int numBytes = end - iBval;
			byte[] inverse = new byte[numBytes];
			int index = 0;
			while (index < numBytes)
			{
				inverse[index++] = (byte)(~bytes[iBval++]);
			}
			Debug.Assert(iBval == end);
			while (inverse[--index] == byte.MaxValue)
			{
				inverse[index] = 0;
			}
			inverse[index]++;
			magnitude = MakeMagnitude(inverse, 0, inverse.Length);
		}
		else
		{
			magnitude = MakeMagnitude(bytes, offset, length);
			sign = ((magnitude.Length != 0) ? 1 : 0);
		}
	}

	private static int[] MakeMagnitude(byte[] bytes, int offset, int length)
	{
		int end = offset + length;
		int firstSignificant;
		for (firstSignificant = offset; firstSignificant < end && bytes[firstSignificant] == 0; firstSignificant++)
		{
		}
		if (firstSignificant >= end)
		{
			return ZeroMagnitude;
		}
		int nInts = (end - firstSignificant + 3) / 4;
		int bCount = (end - firstSignificant) % 4;
		if (bCount == 0)
		{
			bCount = 4;
		}
		if (nInts < 1)
		{
			return ZeroMagnitude;
		}
		int[] mag = new int[nInts];
		int v = 0;
		int magnitudeIndex = 0;
		for (int i = firstSignificant; i < end; i++)
		{
			v <<= 8;
			v |= bytes[i] & 0xFF;
			bCount--;
			if (bCount <= 0)
			{
				mag[magnitudeIndex] = v;
				magnitudeIndex++;
				bCount = 4;
				v = 0;
			}
		}
		if (magnitudeIndex < mag.Length)
		{
			mag[magnitudeIndex] = v;
		}
		return mag;
	}

	public BigInteger(int sign, byte[] bytes)
		: this(sign, bytes, 0, bytes.Length)
	{
	}

	public BigInteger(int sign, byte[] bytes, int offset, int length)
	{
		if (sign < -1 || sign > 1)
		{
			throw new FormatException("Invalid sign value");
		}
		if (sign == 0)
		{
			magnitude = ZeroMagnitude;
			return;
		}
		magnitude = MakeMagnitude(bytes, offset, length);
		this.sign = ((magnitude.Length >= 1) ? sign : 0);
	}

	public BigInteger(int sizeInBits, Random random)
	{
		if (sizeInBits < 0)
		{
			throw new ArgumentException("sizeInBits must be non-negative");
		}
		nBits = -1;
		nBitLength = -1;
		if (sizeInBits == 0)
		{
			magnitude = ZeroMagnitude;
			return;
		}
		int nBytes = GetByteLength(sizeInBits);
		byte[] b = new byte[nBytes];
		random.NextBytes(b);
		b[0] &= rndMask[8 * nBytes - sizeInBits];
		magnitude = MakeMagnitude(b, 0, b.Length);
		sign = ((magnitude.Length >= 1) ? 1 : 0);
	}

	public BigInteger(int bitLength, int certainty, Random random)
	{
		if (bitLength < 2)
		{
			throw new ArithmeticException("bitLength < 2");
		}
		sign = 1;
		nBitLength = bitLength;
		if (bitLength == 2)
		{
			magnitude = ((random.Next(2) == 0) ? Two.magnitude : Three.magnitude);
			return;
		}
		int nBytes = GetByteLength(bitLength);
		byte[] b = new byte[nBytes];
		int xBits = 8 * nBytes - bitLength;
		byte mask = rndMask[xBits];
		while (true)
		{
			random.NextBytes(b);
			b[0] &= mask;
			b[0] |= (byte)(1 << 7 - xBits);
			b[nBytes - 1] |= 1;
			magnitude = MakeMagnitude(b, 0, b.Length);
			nBits = -1;
			mQuote = -1L;
			if (certainty < 1 || CheckProbablePrime(certainty, random))
			{
				break;
			}
			if (bitLength <= 32)
			{
				continue;
			}
			for (int rep = 0; rep < 10000; rep++)
			{
				int i = 33 + random.Next(bitLength - 2);
				magnitude[magnitude.Length - (i >> 5)] ^= 1 << i;
				magnitude[magnitude.Length - 1] ^= random.Next() + 1 << 1;
				mQuote = -1L;
				if (CheckProbablePrime(certainty, random))
				{
					return;
				}
			}
		}
	}

	public BigInteger Abs()
	{
		return (sign >= 0) ? this : Negate();
	}

	private static int[] AddMagnitudes(int[] a, int[] b)
	{
		int tI = a.Length - 1;
		int vI = b.Length - 1;
		long i = 0L;
		while (vI >= 0)
		{
			i += (long)(uint)a[tI] + (long)(uint)b[vI--];
			a[tI--] = (int)i;
			i >>>= 32;
		}
		if (i != 0)
		{
			while (tI >= 0 && ++a[tI--] == 0)
			{
			}
		}
		return a;
	}

	public BigInteger Add(BigInteger value)
	{
		if (sign == 0)
		{
			return value;
		}
		if (sign != value.sign)
		{
			if (value.sign == 0)
			{
				return this;
			}
			if (value.sign < 0)
			{
				return Subtract(value.Negate());
			}
			return value.Subtract(Negate());
		}
		return AddToMagnitude(value.magnitude);
	}

	private BigInteger AddToMagnitude(int[] magToAdd)
	{
		int[] big;
		int[] small;
		if (magnitude.Length < magToAdd.Length)
		{
			big = magToAdd;
			small = magnitude;
		}
		else
		{
			big = magnitude;
			small = magToAdd;
		}
		uint limit = uint.MaxValue;
		if (big.Length == small.Length)
		{
			limit -= (uint)small[0];
		}
		bool possibleOverflow = (uint)big[0] >= limit;
		int[] bigCopy;
		if (possibleOverflow)
		{
			bigCopy = new int[big.Length + 1];
			big.CopyTo(bigCopy, 1);
		}
		else
		{
			bigCopy = (int[])big.Clone();
		}
		bigCopy = AddMagnitudes(bigCopy, small);
		return new BigInteger(sign, bigCopy, possibleOverflow);
	}

	public BigInteger And(BigInteger value)
	{
		if (sign == 0 || value.sign == 0)
		{
			return Zero;
		}
		int[] aMag = ((sign > 0) ? magnitude : Add(One).magnitude);
		int[] bMag = ((value.sign > 0) ? value.magnitude : value.Add(One).magnitude);
		bool resultNeg = sign < 0 && value.sign < 0;
		int resultLength = Math.Max(aMag.Length, bMag.Length);
		int[] resultMag = new int[resultLength];
		int aStart = resultMag.Length - aMag.Length;
		int bStart = resultMag.Length - bMag.Length;
		for (int i = 0; i < resultMag.Length; i++)
		{
			int aWord = ((i >= aStart) ? aMag[i - aStart] : 0);
			int bWord = ((i >= bStart) ? bMag[i - bStart] : 0);
			if (sign < 0)
			{
				aWord = ~aWord;
			}
			if (value.sign < 0)
			{
				bWord = ~bWord;
			}
			resultMag[i] = aWord & bWord;
			if (resultNeg)
			{
				resultMag[i] = ~resultMag[i];
			}
		}
		BigInteger result = new BigInteger(1, resultMag, checkMag: true);
		if (resultNeg)
		{
			result = result.Not();
		}
		return result;
	}

	public BigInteger AndNot(BigInteger val)
	{
		return And(val.Not());
	}

	private int calcBitLength(int indx, int[] mag)
	{
		while (true)
		{
			if (indx >= mag.Length)
			{
				return 0;
			}
			if (mag[indx] != 0)
			{
				break;
			}
			indx++;
		}
		int bitLength = 32 * (mag.Length - indx - 1);
		int firstMag = mag[indx];
		bitLength += BitLen(firstMag);
		if (sign < 0 && (firstMag & -firstMag) == firstMag)
		{
			do
			{
				if (++indx >= mag.Length)
				{
					bitLength--;
					break;
				}
			}
			while (mag[indx] == 0);
		}
		return bitLength;
	}

	private static int BitLen(int w)
	{
		return (w >= 32768) ? ((w >= 8388608) ? ((w >= 134217728) ? ((w >= 536870912) ? ((w < 1073741824) ? 30 : 31) : ((w < 268435456) ? 28 : 29)) : ((w >= 33554432) ? ((w < 67108864) ? 26 : 27) : ((w < 16777216) ? 24 : 25))) : ((w >= 524288) ? ((w >= 2097152) ? ((w < 4194304) ? 22 : 23) : ((w < 1048576) ? 20 : 21)) : ((w >= 131072) ? ((w < 262144) ? 18 : 19) : ((w < 65536) ? 16 : 17)))) : ((w >= 128) ? ((w >= 2048) ? ((w >= 8192) ? ((w < 16384) ? 14 : 15) : ((w < 4096) ? 12 : 13)) : ((w >= 512) ? ((w < 1024) ? 10 : 11) : ((w < 256) ? 8 : 9))) : ((w >= 8) ? ((w >= 32) ? ((w < 64) ? 6 : 7) : ((w < 16) ? 4 : 5)) : ((w >= 2) ? ((w < 4) ? 2 : 3) : ((w >= 1) ? 1 : ((w < 0) ? 32 : 0)))));
	}

	private bool QuickPow2Check()
	{
		return sign > 0 && nBits == 1;
	}

	public int CompareTo(object obj)
	{
		return CompareTo((BigInteger)obj);
	}

	private static int CompareTo(int xIndx, int[] x, int yIndx, int[] y)
	{
		while (xIndx != x.Length && x[xIndx] == 0)
		{
			xIndx++;
		}
		while (yIndx != y.Length && y[yIndx] == 0)
		{
			yIndx++;
		}
		return CompareNoLeadingZeroes(xIndx, x, yIndx, y);
	}

	private static int CompareNoLeadingZeroes(int xIndx, int[] x, int yIndx, int[] y)
	{
		int diff = x.Length - y.Length - (xIndx - yIndx);
		if (diff != 0)
		{
			return (diff >= 0) ? 1 : (-1);
		}
		while (xIndx < x.Length)
		{
			uint v1 = (uint)x[xIndx++];
			uint v2 = (uint)y[yIndx++];
			if (v1 != v2)
			{
				return (v1 >= v2) ? 1 : (-1);
			}
		}
		return 0;
	}

	public int CompareTo(BigInteger value)
	{
		return (sign < value.sign) ? (-1) : ((sign > value.sign) ? 1 : ((sign != 0) ? (sign * CompareNoLeadingZeroes(0, magnitude, 0, value.magnitude)) : 0));
	}

	private int[] Divide(int[] x, int[] y)
	{
		int xStart;
		for (xStart = 0; xStart < x.Length && x[xStart] == 0; xStart++)
		{
		}
		int yStart;
		for (yStart = 0; yStart < y.Length && y[yStart] == 0; yStart++)
		{
		}
		Debug.Assert(yStart < y.Length);
		int xyCmp = CompareNoLeadingZeroes(xStart, x, yStart, y);
		int[] count;
		if (xyCmp > 0)
		{
			int yBitLength = calcBitLength(yStart, y);
			int xBitLength = calcBitLength(xStart, x);
			int shift = xBitLength - yBitLength;
			int iCountStart = 0;
			int cStart = 0;
			int cBitLength = yBitLength;
			int[] iCount;
			int[] c;
			if (shift > 0)
			{
				iCount = new int[(shift >> 5) + 1];
				iCount[0] = 1 << shift % 32;
				c = ShiftLeft(y, shift);
				cBitLength += shift;
			}
			else
			{
				iCount = new int[1] { 1 };
				int len = y.Length - yStart;
				c = new int[len];
				Array.Copy(y, yStart, c, 0, len);
			}
			count = new int[iCount.Length];
			while (true)
			{
				if (cBitLength < xBitLength || CompareNoLeadingZeroes(xStart, x, cStart, c) >= 0)
				{
					Subtract(xStart, x, cStart, c);
					AddMagnitudes(count, iCount);
					while (x[xStart] == 0)
					{
						if (++xStart == x.Length)
						{
							return count;
						}
					}
					xBitLength = 32 * (x.Length - xStart - 1) + BitLen(x[xStart]);
					if (xBitLength <= yBitLength)
					{
						if (xBitLength < yBitLength)
						{
							return count;
						}
						xyCmp = CompareNoLeadingZeroes(xStart, x, yStart, y);
						if (xyCmp <= 0)
						{
							break;
						}
					}
				}
				shift = cBitLength - xBitLength;
				if (shift == 1)
				{
					uint firstC = (uint)c[cStart] >> 1;
					uint firstX = (uint)x[xStart];
					if (firstC > firstX)
					{
						shift++;
					}
				}
				if (shift < 2)
				{
					ShiftRightOneInPlace(cStart, c);
					cBitLength--;
					ShiftRightOneInPlace(iCountStart, iCount);
				}
				else
				{
					ShiftRightInPlace(cStart, c, shift);
					cBitLength -= shift;
					ShiftRightInPlace(iCountStart, iCount, shift);
				}
				for (; c[cStart] == 0; cStart++)
				{
				}
				for (; iCount[iCountStart] == 0; iCountStart++)
				{
				}
			}
		}
		else
		{
			count = new int[1];
		}
		if (xyCmp == 0)
		{
			AddMagnitudes(count, One.magnitude);
			Array.Clear(x, xStart, x.Length - xStart);
		}
		return count;
	}

	public BigInteger Divide(BigInteger val)
	{
		if (val.sign == 0)
		{
			throw new ArithmeticException("Division by zero error");
		}
		if (sign == 0)
		{
			return Zero;
		}
		if (val.QuickPow2Check())
		{
			BigInteger result = Abs().ShiftRight(val.Abs().BitLength - 1);
			return (val.sign == sign) ? result : result.Negate();
		}
		int[] mag = (int[])magnitude.Clone();
		return new BigInteger(sign * val.sign, Divide(mag, val.magnitude), checkMag: true);
	}

	public BigInteger[] DivideAndRemainder(BigInteger val)
	{
		if (val.sign == 0)
		{
			throw new ArithmeticException("Division by zero error");
		}
		BigInteger[] biggies = new BigInteger[2];
		if (sign == 0)
		{
			biggies[0] = Zero;
			biggies[1] = Zero;
		}
		else if (val.QuickPow2Check())
		{
			int e = val.Abs().BitLength - 1;
			BigInteger quotient = Abs().ShiftRight(e);
			int[] remainder = LastNBits(e);
			biggies[0] = ((val.sign == sign) ? quotient : quotient.Negate());
			biggies[1] = new BigInteger(sign, remainder, checkMag: true);
		}
		else
		{
			int[] remainder2 = (int[])magnitude.Clone();
			int[] quotient2 = Divide(remainder2, val.magnitude);
			biggies[0] = new BigInteger(sign * val.sign, quotient2, checkMag: true);
			biggies[1] = new BigInteger(sign, remainder2, checkMag: true);
		}
		return biggies;
	}

	public override bool Equals(object obj)
	{
		if (obj == this)
		{
			return true;
		}
		if (!(obj is BigInteger biggie))
		{
			return false;
		}
		if (biggie.sign != sign || biggie.magnitude.Length != magnitude.Length)
		{
			return false;
		}
		for (int i = 0; i < magnitude.Length; i++)
		{
			if (biggie.magnitude[i] != magnitude[i])
			{
				return false;
			}
		}
		return true;
	}

	public BigInteger Gcd(BigInteger value)
	{
		if (value.sign == 0)
		{
			return Abs();
		}
		if (sign == 0)
		{
			return value.Abs();
		}
		BigInteger u = this;
		BigInteger v = value;
		while (v.sign != 0)
		{
			BigInteger r = u.Mod(v);
			u = v;
			v = r;
		}
		return u;
	}

	public override int GetHashCode()
	{
		int hc = magnitude.Length;
		if (magnitude.Length != 0)
		{
			hc ^= magnitude[0];
			if (magnitude.Length > 1)
			{
				hc ^= magnitude[magnitude.Length - 1];
			}
		}
		return (sign < 0) ? (~hc) : hc;
	}

	private BigInteger Inc()
	{
		if (sign == 0)
		{
			return One;
		}
		if (sign < 0)
		{
			return new BigInteger(-1, doSubBigLil(magnitude, One.magnitude), checkMag: true);
		}
		return AddToMagnitude(One.magnitude);
	}

	public bool IsProbablePrime(int certainty)
	{
		if (certainty <= 0)
		{
			return true;
		}
		BigInteger i = Abs();
		if (!i.TestBit(0))
		{
			return i.Equals(Two);
		}
		if (i.Equals(One))
		{
			return false;
		}
		return i.CheckProbablePrime(certainty, RandomSource);
	}

	private bool CheckProbablePrime(int certainty, Random random)
	{
		Debug.Assert(certainty > 0);
		Debug.Assert(CompareTo(Two) > 0);
		Debug.Assert(TestBit(0));
		int numLists = Math.Min(BitLength - 1, primeLists.Length);
		for (int i = 0; i < numLists; i++)
		{
			int test = Remainder(primeProducts[i]);
			int[] primeList = primeLists[i];
			foreach (int prime in primeList)
			{
				if (test % prime == 0)
				{
					return BitLength < 16 && IntValue == prime;
				}
			}
		}
		return RabinMillerTest(certainty, random);
	}

	internal bool RabinMillerTest(int certainty, Random random)
	{
		Debug.Assert(certainty > 0);
		Debug.Assert(BitLength > 2);
		Debug.Assert(TestBit(0));
		BigInteger nMinusOne = Subtract(One);
		int s = nMinusOne.GetLowestSetBit();
		BigInteger r = nMinusOne.ShiftRight(s);
		Debug.Assert(s >= 1);
		while (true)
		{
			BigInteger a = new BigInteger(BitLength, random);
			if (a.CompareTo(One) <= 0 || a.CompareTo(nMinusOne) >= 0)
			{
				continue;
			}
			BigInteger y = a.ModPow(r, this);
			if (!y.Equals(One))
			{
				int i = 0;
				while (!y.Equals(nMinusOne))
				{
					if (++i == s)
					{
						return false;
					}
					y = y.ModPow(Two, this);
					if (y.Equals(One))
					{
						return false;
					}
				}
			}
			certainty -= 2;
			if (certainty <= 0)
			{
				break;
			}
		}
		return true;
	}

	public BigInteger Max(BigInteger value)
	{
		return (CompareTo(value) > 0) ? this : value;
	}

	public BigInteger Min(BigInteger value)
	{
		return (CompareTo(value) < 0) ? this : value;
	}

	public BigInteger Mod(BigInteger m)
	{
		if (m.sign < 1)
		{
			throw new ArithmeticException("Modulus must be positive");
		}
		BigInteger biggie = Remainder(m);
		return (biggie.sign >= 0) ? biggie : biggie.Add(m);
	}

	public BigInteger ModInverse(BigInteger m)
	{
		if (m.sign < 1)
		{
			throw new ArithmeticException("Modulus must be positive");
		}
		BigInteger x = new BigInteger();
		BigInteger gcd = ExtEuclid(Mod(m), m, x, null);
		if (!gcd.Equals(One))
		{
			throw new ArithmeticException("Numbers not relatively prime.");
		}
		if (x.sign < 0)
		{
			x.sign = 1;
			x.magnitude = doSubBigLil(m.magnitude, x.magnitude);
		}
		return x;
	}

	private static BigInteger ExtEuclid(BigInteger a, BigInteger b, BigInteger u1Out, BigInteger u2Out)
	{
		BigInteger u1 = One;
		BigInteger u2 = a;
		BigInteger v1 = Zero;
		BigInteger v2 = b;
		while (v2.sign > 0)
		{
			BigInteger[] q = u2.DivideAndRemainder(v2);
			BigInteger tmp2 = v1.Multiply(q[0]);
			BigInteger tn = u1.Subtract(tmp2);
			u1 = v1;
			v1 = tn;
			u2 = v2;
			v2 = q[1];
		}
		if (u1Out != null)
		{
			u1Out.sign = u1.sign;
			u1Out.magnitude = u1.magnitude;
		}
		if (u2Out != null)
		{
			BigInteger tmp = u1.Multiply(a);
			tmp = u2.Subtract(tmp);
			BigInteger res = tmp.Divide(b);
			u2Out.sign = res.sign;
			u2Out.magnitude = res.magnitude;
		}
		return u2;
	}

	private static void ZeroOut(int[] x)
	{
		Array.Clear(x, 0, x.Length);
	}

	public BigInteger ModPow(BigInteger exponent, BigInteger m)
	{
		if (m.sign < 1)
		{
			throw new ArithmeticException("Modulus must be positive");
		}
		if (m.Equals(One))
		{
			return Zero;
		}
		if (exponent.sign == 0)
		{
			return One;
		}
		if (sign == 0)
		{
			return Zero;
		}
		int[] zVal = null;
		int[] yAccum = null;
		bool useMonty = (m.magnitude[m.magnitude.Length - 1] & 1) == 1;
		long mQ = 0L;
		if (useMonty)
		{
			mQ = m.GetMQuote();
			BigInteger tmp = ShiftLeft(32 * m.magnitude.Length).Mod(m);
			zVal = tmp.magnitude;
			useMonty = zVal.Length <= m.magnitude.Length;
			if (useMonty)
			{
				yAccum = new int[m.magnitude.Length + 1];
				if (zVal.Length < m.magnitude.Length)
				{
					int[] longZ = new int[m.magnitude.Length];
					zVal.CopyTo(longZ, longZ.Length - zVal.Length);
					zVal = longZ;
				}
			}
		}
		if (!useMonty)
		{
			if (magnitude.Length <= m.magnitude.Length)
			{
				zVal = new int[m.magnitude.Length];
				magnitude.CopyTo(zVal, zVal.Length - magnitude.Length);
			}
			else
			{
				BigInteger tmp2 = Remainder(m);
				zVal = new int[m.magnitude.Length];
				tmp2.magnitude.CopyTo(zVal, zVal.Length - tmp2.magnitude.Length);
			}
			yAccum = new int[m.magnitude.Length * 2];
		}
		int[] yVal = new int[m.magnitude.Length];
		for (int i = 0; i < exponent.magnitude.Length; i++)
		{
			int v = exponent.magnitude[i];
			int bits = 0;
			if (i == 0)
			{
				while (v > 0)
				{
					v <<= 1;
					bits++;
				}
				zVal.CopyTo(yVal, 0);
				v <<= 1;
				bits++;
			}
			while (v != 0)
			{
				if (useMonty)
				{
					MultiplyMonty(yAccum, yVal, yVal, m.magnitude, mQ);
				}
				else
				{
					Square(yAccum, yVal);
					Remainder(yAccum, m.magnitude);
					Array.Copy(yAccum, yAccum.Length - yVal.Length, yVal, 0, yVal.Length);
					ZeroOut(yAccum);
				}
				bits++;
				if (v < 0)
				{
					if (useMonty)
					{
						MultiplyMonty(yAccum, yVal, zVal, m.magnitude, mQ);
					}
					else
					{
						Multiply(yAccum, yVal, zVal);
						Remainder(yAccum, m.magnitude);
						Array.Copy(yAccum, yAccum.Length - yVal.Length, yVal, 0, yVal.Length);
						ZeroOut(yAccum);
					}
				}
				v <<= 1;
			}
			for (; bits < 32; bits++)
			{
				if (useMonty)
				{
					MultiplyMonty(yAccum, yVal, yVal, m.magnitude, mQ);
					continue;
				}
				Square(yAccum, yVal);
				Remainder(yAccum, m.magnitude);
				Array.Copy(yAccum, yAccum.Length - yVal.Length, yVal, 0, yVal.Length);
				ZeroOut(yAccum);
			}
		}
		if (useMonty)
		{
			ZeroOut(zVal);
			zVal[zVal.Length - 1] = 1;
			MultiplyMonty(yAccum, yVal, zVal, m.magnitude, mQ);
		}
		BigInteger result = new BigInteger(1, yVal, checkMag: true);
		return (exponent.sign > 0) ? result : result.ModInverse(m);
	}

	private static int[] Square(int[] w, int[] x)
	{
		int wBase = w.Length - 1;
		ulong u2;
		ulong u1;
		for (int i = x.Length - 1; i != 0; i--)
		{
			ulong v = (uint)x[i];
			u1 = v * v;
			u2 = u1 >> 32;
			u1 = (uint)u1;
			u1 += (uint)w[wBase];
			w[wBase] = (int)u1;
			ulong c = u2 + (u1 >> 32);
			for (int j = i - 1; j >= 0; j--)
			{
				wBase--;
				u1 = v * (uint)x[j];
				u2 = u1 >> 31;
				u1 <<= 1;
				u1 += c + (uint)w[wBase];
				w[wBase] = (int)u1;
				c = u2 + (u1 >> 32);
			}
			c += (uint)w[--wBase];
			w[wBase] = (int)c;
			if (--wBase >= 0)
			{
				w[wBase] = (int)(c >> 32);
			}
			else
			{
				Debug.Assert((int)(c >> 32) == 0);
			}
			wBase += i;
		}
		u1 = (uint)x[0];
		u1 *= u1;
		u2 = u1 >> 32;
		u1 &= 0xFFFFFFFFu;
		u1 += (uint)w[wBase];
		w[wBase] = (int)u1;
		if (--wBase >= 0)
		{
			w[wBase] = (int)(u2 + (u1 >> 32) + (uint)w[wBase]);
		}
		else
		{
			Debug.Assert((int)(u2 + (u1 >> 32)) == 0);
		}
		return w;
	}

	private static int[] Multiply(int[] x, int[] y, int[] z)
	{
		int i = z.Length;
		if (i < 1)
		{
			return x;
		}
		int xBase = x.Length - y.Length;
		long val;
		while (true)
		{
			long a = z[--i] & 0xFFFFFFFFu;
			val = 0L;
			for (int j = y.Length - 1; j >= 0; j--)
			{
				val += a * (y[j] & 0xFFFFFFFFu) + (x[xBase + j] & 0xFFFFFFFFu);
				x[xBase + j] = (int)val;
				val >>>= 32;
			}
			xBase--;
			if (i < 1)
			{
				break;
			}
			x[xBase] = (int)val;
		}
		if (xBase >= 0)
		{
			x[xBase] = (int)val;
		}
		else
		{
			Debug.Assert(val == 0);
		}
		return x;
	}

	private static long FastExtEuclid(long a, long b, long[] uOut)
	{
		long u1 = 1L;
		long u2 = a;
		long v1 = 0L;
		long v2 = b;
		while (v2 > 0)
		{
			long q = u2 / v2;
			long tn = u1 - v1 * q;
			u1 = v1;
			v1 = tn;
			tn = u2 - v2 * q;
			u2 = v2;
			v2 = tn;
		}
		uOut[0] = u1;
		uOut[1] = (u2 - u1 * a) / b;
		return u2;
	}

	private static long FastModInverse(long v, long m)
	{
		if (m < 1)
		{
			throw new ArithmeticException("Modulus must be positive");
		}
		long[] x = new long[2];
		long gcd = FastExtEuclid(v, m, x);
		if (gcd != 1)
		{
			throw new ArithmeticException("Numbers not relatively prime.");
		}
		if (x[0] < 0)
		{
			x[0] += m;
		}
		return x[0];
	}

	private long GetMQuote()
	{
		Debug.Assert(sign > 0);
		if (mQuote != -1)
		{
			return mQuote;
		}
		if (magnitude.Length == 0 || (magnitude[magnitude.Length - 1] & 1) == 0)
		{
			return -1L;
		}
		long v = (~magnitude[magnitude.Length - 1] | 1) & 0xFFFFFFFFu;
		mQuote = FastModInverse(v, 4294967296L);
		return mQuote;
	}

	private static void MultiplyMonty(int[] a, int[] x, int[] y, int[] m, long mQuote)
	{
		if (m.Length == 1)
		{
			x[0] = (int)MultiplyMontyNIsOne((uint)x[0], (uint)y[0], (uint)m[0], (ulong)mQuote);
			return;
		}
		int k = m.Length;
		int nMinus1 = k - 1;
		long y_0 = y[nMinus1] & 0xFFFFFFFFu;
		Array.Clear(a, 0, k + 1);
		for (int i = k; i > 0; i--)
		{
			long x_i = x[i - 1] & 0xFFFFFFFFu;
			long u = ((((a[k] & 0xFFFFFFFFu) + ((x_i * y_0) & 0xFFFFFFFFu)) & 0xFFFFFFFFu) * mQuote) & 0xFFFFFFFFu;
			long prod1 = x_i * y_0;
			long prod2 = u * (m[nMinus1] & 0xFFFFFFFFu);
			long tmp = (a[k] & 0xFFFFFFFFu) + (prod1 & 0xFFFFFFFFu) + (prod2 & 0xFFFFFFFFu);
			long carry = (prod1 >>> 32) + (prod2 >>> 32) + (tmp >>> 32);
			for (int j = nMinus1; j > 0; j--)
			{
				prod1 = x_i * (y[j - 1] & 0xFFFFFFFFu);
				prod2 = u * (m[j - 1] & 0xFFFFFFFFu);
				tmp = (a[j] & 0xFFFFFFFFu) + (prod1 & 0xFFFFFFFFu) + (prod2 & 0xFFFFFFFFu) + (carry & 0xFFFFFFFFu);
				carry = (carry >>> 32) + (prod1 >>> 32) + (prod2 >>> 32) + (tmp >>> 32);
				a[j + 1] = (int)tmp;
			}
			carry += a[0] & 0xFFFFFFFFu;
			a[1] = (int)carry;
			a[0] = (int)(carry >>> 32);
		}
		if (CompareTo(0, a, 0, m) >= 0)
		{
			Subtract(0, a, 0, m);
		}
		Array.Copy(a, 1, x, 0, k);
	}

	private static uint MultiplyMontyNIsOne(uint x, uint y, uint m, ulong mQuote)
	{
		ulong um = m;
		ulong prod1 = (ulong)x * (ulong)y;
		ulong u = (prod1 * mQuote) & UIMASK;
		ulong prod2 = u * um;
		ulong tmp = (prod1 & UIMASK) + (prod2 & UIMASK);
		ulong carry = (prod1 >> 32) + (prod2 >> 32) + (tmp >> 32);
		if (carry > um)
		{
			carry -= um;
		}
		return (uint)(carry & UIMASK);
	}

	public BigInteger Multiply(BigInteger val)
	{
		if (sign == 0 || val.sign == 0)
		{
			return Zero;
		}
		if (val.QuickPow2Check())
		{
			BigInteger result = ShiftLeft(val.Abs().BitLength - 1);
			return (val.sign > 0) ? result : result.Negate();
		}
		if (QuickPow2Check())
		{
			BigInteger result2 = val.ShiftLeft(Abs().BitLength - 1);
			return (sign > 0) ? result2 : result2.Negate();
		}
		int resLength = (BitLength + val.BitLength) / 32 + 1;
		int[] res = new int[resLength];
		if (val == this)
		{
			Square(res, magnitude);
		}
		else
		{
			Multiply(res, magnitude, val.magnitude);
		}
		return new BigInteger(sign * val.sign, res, checkMag: true);
	}

	public BigInteger Negate()
	{
		if (sign == 0)
		{
			return this;
		}
		return new BigInteger(-sign, magnitude, checkMag: false);
	}

	public BigInteger NextProbablePrime()
	{
		if (sign < 0)
		{
			throw new ArithmeticException("Cannot be called on value < 0");
		}
		if (CompareTo(Two) < 0)
		{
			return Two;
		}
		BigInteger i = Inc().SetBit(0);
		while (!i.CheckProbablePrime(100, RandomSource))
		{
			i = i.Add(Two);
		}
		return i;
	}

	public BigInteger Not()
	{
		return Inc().Negate();
	}

	public BigInteger Pow(int exp)
	{
		if (exp < 0)
		{
			throw new ArithmeticException("Negative exponent");
		}
		if (exp == 0)
		{
			return One;
		}
		if (sign == 0 || Equals(One))
		{
			return this;
		}
		BigInteger y = One;
		BigInteger z = this;
		while (true)
		{
			if ((exp & 1) == 1)
			{
				y = y.Multiply(z);
			}
			exp >>= 1;
			if (exp == 0)
			{
				break;
			}
			z = z.Multiply(z);
		}
		return y;
	}

	public static BigInteger ProbablePrime(int bitLength, Random random)
	{
		return new BigInteger(bitLength, 100, random);
	}

	private int Remainder(int m)
	{
		Debug.Assert(m > 0);
		long acc = 0L;
		for (int pos = 0; pos < magnitude.Length; pos++)
		{
			long posVal = (uint)magnitude[pos];
			acc = ((acc << 32) | posVal) % m;
		}
		return (int)acc;
	}

	private int[] Remainder(int[] x, int[] y)
	{
		int xStart;
		for (xStart = 0; xStart < x.Length && x[xStart] == 0; xStart++)
		{
		}
		int yStart;
		for (yStart = 0; yStart < y.Length && y[yStart] == 0; yStart++)
		{
		}
		Debug.Assert(yStart < y.Length);
		int xyCmp = CompareNoLeadingZeroes(xStart, x, yStart, y);
		if (xyCmp > 0)
		{
			int yBitLength = calcBitLength(yStart, y);
			int xBitLength = calcBitLength(xStart, x);
			int shift = xBitLength - yBitLength;
			int cStart = 0;
			int cBitLength = yBitLength;
			int[] c;
			if (shift > 0)
			{
				c = ShiftLeft(y, shift);
				cBitLength += shift;
				Debug.Assert(c[0] != 0);
			}
			else
			{
				int len = y.Length - yStart;
				c = new int[len];
				Array.Copy(y, yStart, c, 0, len);
			}
			while (true)
			{
				if (cBitLength < xBitLength || CompareNoLeadingZeroes(xStart, x, cStart, c) >= 0)
				{
					Subtract(xStart, x, cStart, c);
					while (x[xStart] == 0)
					{
						if (++xStart == x.Length)
						{
							return x;
						}
					}
					xBitLength = 32 * (x.Length - xStart - 1) + BitLen(x[xStart]);
					if (xBitLength <= yBitLength)
					{
						if (xBitLength < yBitLength)
						{
							return x;
						}
						xyCmp = CompareNoLeadingZeroes(xStart, x, yStart, y);
						if (xyCmp <= 0)
						{
							break;
						}
					}
				}
				shift = cBitLength - xBitLength;
				if (shift == 1)
				{
					uint firstC = (uint)c[cStart] >> 1;
					uint firstX = (uint)x[xStart];
					if (firstC > firstX)
					{
						shift++;
					}
				}
				if (shift < 2)
				{
					ShiftRightOneInPlace(cStart, c);
					cBitLength--;
				}
				else
				{
					ShiftRightInPlace(cStart, c, shift);
					cBitLength -= shift;
				}
				for (; c[cStart] == 0; cStart++)
				{
				}
			}
		}
		if (xyCmp == 0)
		{
			Array.Clear(x, xStart, x.Length - xStart);
		}
		return x;
	}

	public BigInteger Remainder(BigInteger n)
	{
		if (n.sign == 0)
		{
			throw new ArithmeticException("Division by zero error");
		}
		if (sign == 0)
		{
			return Zero;
		}
		if (n.magnitude.Length == 1)
		{
			int val = n.magnitude[0];
			if (val > 0)
			{
				if (val == 1)
				{
					return Zero;
				}
				int rem = Remainder(val);
				return (rem == 0) ? Zero : new BigInteger(sign, new int[1] { rem }, checkMag: false);
			}
		}
		if (CompareNoLeadingZeroes(0, magnitude, 0, n.magnitude) < 0)
		{
			return this;
		}
		int[] result;
		if (n.QuickPow2Check())
		{
			result = LastNBits(n.Abs().BitLength - 1);
		}
		else
		{
			result = (int[])magnitude.Clone();
			result = Remainder(result, n.magnitude);
		}
		return new BigInteger(sign, result, checkMag: true);
	}

	private int[] LastNBits(int n)
	{
		if (n < 1)
		{
			return ZeroMagnitude;
		}
		int numWords = (n + 32 - 1) / 32;
		numWords = Math.Min(numWords, magnitude.Length);
		int[] result = new int[numWords];
		Array.Copy(magnitude, magnitude.Length - numWords, result, 0, numWords);
		int hiBits = n % 32;
		if (hiBits != 0)
		{
			result[0] &= ~(-1 << hiBits);
		}
		return result;
	}

	private static int[] ShiftLeft(int[] mag, int n)
	{
		int nInts = n >>> 5;
		int nBits = n & 0x1F;
		int magLen = mag.Length;
		int[] newMag;
		if (nBits == 0)
		{
			newMag = new int[magLen + nInts];
			mag.CopyTo(newMag, 0);
		}
		else
		{
			int i = 0;
			int nBits2 = 32 - nBits;
			int highBits = mag[0] >>> nBits2;
			if (highBits != 0)
			{
				newMag = new int[magLen + nInts + 1];
				newMag[i++] = highBits;
			}
			else
			{
				newMag = new int[magLen + nInts];
			}
			int k = mag[0];
			for (int j = 0; j < magLen - 1; j++)
			{
				int next = mag[j + 1];
				newMag[i++] = (k << nBits) | (next >>> nBits2);
				k = next;
			}
			newMag[i] = mag[magLen - 1] << nBits;
		}
		return newMag;
	}

	public BigInteger ShiftLeft(int n)
	{
		if (sign == 0 || magnitude.Length == 0)
		{
			return Zero;
		}
		if (n == 0)
		{
			return this;
		}
		if (n < 0)
		{
			return ShiftRight(-n);
		}
		BigInteger result = new BigInteger(sign, ShiftLeft(magnitude, n), checkMag: true);
		if (nBits != -1)
		{
			result.nBits = ((sign > 0) ? nBits : (nBits + n));
		}
		if (nBitLength != -1)
		{
			result.nBitLength = nBitLength + n;
		}
		return result;
	}

	private static void ShiftRightInPlace(int start, int[] mag, int n)
	{
		int nInts = (n >>> 5) + start;
		int nBits = n & 0x1F;
		int magEnd = mag.Length - 1;
		if (nInts != start)
		{
			int delta = nInts - start;
			for (int k = magEnd; k >= nInts; k--)
			{
				mag[k] = mag[k - delta];
			}
			for (int j = nInts - 1; j >= start; j--)
			{
				mag[j] = 0;
			}
		}
		if (nBits != 0)
		{
			int nBits2 = 32 - nBits;
			int l = mag[magEnd];
			for (int i = magEnd; i > nInts; i--)
			{
				int next = mag[i - 1];
				mag[i] = (l >>> nBits) | (next << nBits2);
				l = next;
			}
			mag[nInts] >>>= nBits;
		}
	}

	private static void ShiftRightOneInPlace(int start, int[] mag)
	{
		int i = mag.Length;
		int j = mag[i - 1];
		while (--i > start)
		{
			int next = mag[i - 1];
			mag[i] = (j >>> 1) | (next << 31);
			j = next;
		}
		mag[start] >>>= 1;
	}

	public BigInteger ShiftRight(int n)
	{
		if (n == 0)
		{
			return this;
		}
		if (n < 0)
		{
			return ShiftLeft(-n);
		}
		if (n >= BitLength)
		{
			return (sign < 0) ? One.Negate() : Zero;
		}
		int resultLength = BitLength - n + 31 >> 5;
		int[] res = new int[resultLength];
		int numInts = n >> 5;
		int numBits = n & 0x1F;
		if (numBits == 0)
		{
			Array.Copy(magnitude, 0, res, 0, res.Length);
		}
		else
		{
			int numBits2 = 32 - numBits;
			int magPos = magnitude.Length - 1 - numInts;
			for (int i = resultLength - 1; i >= 0; i--)
			{
				res[i] = magnitude[magPos--] >>> numBits;
				if (magPos >= 0)
				{
					res[i] |= magnitude[magPos] << numBits2;
				}
			}
		}
		Debug.Assert(res[0] != 0);
		return new BigInteger(sign, res, checkMag: false);
	}

	private static int[] Subtract(int xStart, int[] x, int yStart, int[] y)
	{
		Debug.Assert(yStart < y.Length);
		Debug.Assert(x.Length - xStart >= y.Length - yStart);
		int iT = x.Length;
		int iV = y.Length;
		int borrow = 0;
		do
		{
			long i = (x[--iT] & 0xFFFFFFFFu) - (y[--iV] & 0xFFFFFFFFu) + borrow;
			x[iT] = (int)i;
			borrow = (int)(i >> 63);
		}
		while (iV > yStart);
		if (borrow != 0)
		{
			while (--x[--iT] == -1)
			{
			}
		}
		return x;
	}

	public BigInteger Subtract(BigInteger n)
	{
		if (n.sign == 0)
		{
			return this;
		}
		if (sign == 0)
		{
			return n.Negate();
		}
		if (sign != n.sign)
		{
			return Add(n.Negate());
		}
		int compare = CompareNoLeadingZeroes(0, magnitude, 0, n.magnitude);
		if (compare == 0)
		{
			return Zero;
		}
		BigInteger bigun;
		BigInteger lilun;
		if (compare < 0)
		{
			bigun = n;
			lilun = this;
		}
		else
		{
			bigun = this;
			lilun = n;
		}
		return new BigInteger(sign * compare, doSubBigLil(bigun.magnitude, lilun.magnitude), checkMag: true);
	}

	private static int[] doSubBigLil(int[] bigMag, int[] lilMag)
	{
		int[] res = (int[])bigMag.Clone();
		return Subtract(0, res, 0, lilMag);
	}

	public byte[] ToByteArray()
	{
		return ToByteArray(unsigned: false);
	}

	public byte[] ToByteArrayUnsigned()
	{
		return ToByteArray(unsigned: true);
	}

	private byte[] ToByteArray(bool unsigned)
	{
		if (sign == 0)
		{
			return unsigned ? ZeroEncoding : new byte[1];
		}
		int nBits = ((unsigned && sign > 0) ? BitLength : (BitLength + 1));
		int nBytes = GetByteLength(nBits);
		byte[] bytes = new byte[nBytes];
		int magIndex = magnitude.Length;
		int bytesIndex = bytes.Length;
		if (sign > 0)
		{
			while (magIndex > 1)
			{
				uint mag = (uint)magnitude[--magIndex];
				bytes[--bytesIndex] = (byte)mag;
				bytes[--bytesIndex] = (byte)(mag >> 8);
				bytes[--bytesIndex] = (byte)(mag >> 16);
				bytes[--bytesIndex] = (byte)(mag >> 24);
			}
			uint lastMag;
			for (lastMag = (uint)magnitude[0]; lastMag > 255; lastMag >>= 8)
			{
				bytes[--bytesIndex] = (byte)lastMag;
			}
			bytes[--bytesIndex] = (byte)lastMag;
		}
		else
		{
			bool carry = true;
			while (magIndex > 1)
			{
				uint mag2 = (uint)(~magnitude[--magIndex]);
				if (carry)
				{
					carry = ++mag2 == 0;
				}
				bytes[--bytesIndex] = (byte)mag2;
				bytes[--bytesIndex] = (byte)(mag2 >> 8);
				bytes[--bytesIndex] = (byte)(mag2 >> 16);
				bytes[--bytesIndex] = (byte)(mag2 >> 24);
			}
			uint lastMag2 = (uint)magnitude[0];
			if (carry)
			{
				lastMag2--;
			}
			while (lastMag2 > 255)
			{
				bytes[--bytesIndex] = (byte)(~lastMag2);
				lastMag2 >>= 8;
			}
			bytes[--bytesIndex] = (byte)(~lastMag2);
			if (bytesIndex > 0)
			{
				bytes[--bytesIndex] = byte.MaxValue;
			}
		}
		return bytes;
	}

	public override string ToString()
	{
		return ToString(10);
	}

	public string ToString(int radix)
	{
		if (radix != 2 && radix != 10 && radix != 16)
		{
			throw new FormatException("Only bases 2, 10, 16 are allowed");
		}
		if (magnitude == null)
		{
			return "null";
		}
		if (sign == 0)
		{
			return "0";
		}
		Debug.Assert(magnitude.Length != 0);
		StringBuilder sb = new StringBuilder();
		switch (radix)
		{
		case 16:
		{
			sb.Append(magnitude[0].ToString("x"));
			for (int k = 1; k < magnitude.Length; k++)
			{
				sb.Append(magnitude[k].ToString("x8"));
			}
			break;
		}
		case 2:
		{
			sb.Append('1');
			for (int j = BitLength - 2; j >= 0; j--)
			{
				sb.Append(TestBit(j) ? '1' : '0');
			}
			break;
		}
		default:
		{
			IList S = new ArrayList();
			BigInteger bs = ValueOf(radix);
			BigInteger u = Abs();
			while (u.sign != 0)
			{
				BigInteger b = u.Mod(bs);
				if (b.sign == 0)
				{
					S.Add("0");
				}
				else
				{
					S.Add(b.magnitude[0].ToString("d"));
				}
				u = u.Divide(bs);
			}
			for (int i = S.Count - 1; i >= 0; i--)
			{
				sb.Append((string)S[i]);
			}
			break;
		}
		}
		string s = sb.ToString();
		Debug.Assert(s.Length > 0);
		if (s[0] == '0')
		{
			int nonZeroPos = 0;
			while (s[++nonZeroPos] == '0')
			{
			}
			s = s.Substring(nonZeroPos);
		}
		if (sign == -1)
		{
			s = "-" + s;
		}
		return s;
	}

	private static BigInteger createUValueOf(ulong value)
	{
		int msw = (int)(value >> 32);
		int lsw = (int)value;
		if (msw != 0)
		{
			return new BigInteger(1, new int[2] { msw, lsw }, checkMag: false);
		}
		if (lsw != 0)
		{
			BigInteger i = new BigInteger(1, new int[1] { lsw }, checkMag: false);
			if ((lsw & -lsw) == lsw)
			{
				i.nBits = 1;
			}
			return i;
		}
		return Zero;
	}

	private static BigInteger createValueOf(long value)
	{
		if (value < 0)
		{
			if (value == long.MinValue)
			{
				return createValueOf(~value).Not();
			}
			return createValueOf(-value).Negate();
		}
		return createUValueOf((ulong)value);
	}

	public static BigInteger ValueOf(long value)
	{
		if ((ulong)value <= 3uL)
		{
			switch (value)
			{
			case 0L:
				return Zero;
			case 1L:
				return One;
			case 2L:
				return Two;
			case 3L:
				return Three;
			}
		}
		if (value == 10)
		{
			return Ten;
		}
		return createValueOf(value);
	}

	public int GetLowestSetBit()
	{
		if (sign == 0)
		{
			return -1;
		}
		int w = magnitude.Length;
		while (--w > 0 && magnitude[w] == 0)
		{
		}
		int word = magnitude[w];
		Debug.Assert(word != 0);
		int b = ((((uint)word & 0xFFFFu) != 0) ? (((word & 0xFF) == 0) ? 23 : 31) : (((word & 0xFF0000) == 0) ? 7 : 15));
		while (b > 0 && word << b != int.MinValue)
		{
			b--;
		}
		return (magnitude.Length - w) * 32 - (b + 1);
	}

	public bool TestBit(int n)
	{
		if (n < 0)
		{
			throw new ArithmeticException("Bit position must not be negative");
		}
		if (sign < 0)
		{
			return !Not().TestBit(n);
		}
		int wordNum = n / 32;
		if (wordNum >= magnitude.Length)
		{
			return false;
		}
		int word = magnitude[magnitude.Length - 1 - wordNum];
		return ((word >> n % 32) & 1) > 0;
	}

	public BigInteger Or(BigInteger value)
	{
		if (sign == 0)
		{
			return value;
		}
		if (value.sign == 0)
		{
			return this;
		}
		int[] aMag = ((sign > 0) ? magnitude : Add(One).magnitude);
		int[] bMag = ((value.sign > 0) ? value.magnitude : value.Add(One).magnitude);
		bool resultNeg = sign < 0 || value.sign < 0;
		int resultLength = Math.Max(aMag.Length, bMag.Length);
		int[] resultMag = new int[resultLength];
		int aStart = resultMag.Length - aMag.Length;
		int bStart = resultMag.Length - bMag.Length;
		for (int i = 0; i < resultMag.Length; i++)
		{
			int aWord = ((i >= aStart) ? aMag[i - aStart] : 0);
			int bWord = ((i >= bStart) ? bMag[i - bStart] : 0);
			if (sign < 0)
			{
				aWord = ~aWord;
			}
			if (value.sign < 0)
			{
				bWord = ~bWord;
			}
			resultMag[i] = aWord | bWord;
			if (resultNeg)
			{
				resultMag[i] = ~resultMag[i];
			}
		}
		BigInteger result = new BigInteger(1, resultMag, checkMag: true);
		if (resultNeg)
		{
			result = result.Not();
		}
		return result;
	}

	public BigInteger Xor(BigInteger value)
	{
		if (sign == 0)
		{
			return value;
		}
		if (value.sign == 0)
		{
			return this;
		}
		int[] aMag = ((sign > 0) ? magnitude : Add(One).magnitude);
		int[] bMag = ((value.sign > 0) ? value.magnitude : value.Add(One).magnitude);
		bool resultNeg = (sign < 0 && value.sign >= 0) || (sign >= 0 && value.sign < 0);
		int resultLength = Math.Max(aMag.Length, bMag.Length);
		int[] resultMag = new int[resultLength];
		int aStart = resultMag.Length - aMag.Length;
		int bStart = resultMag.Length - bMag.Length;
		for (int i = 0; i < resultMag.Length; i++)
		{
			int aWord = ((i >= aStart) ? aMag[i - aStart] : 0);
			int bWord = ((i >= bStart) ? bMag[i - bStart] : 0);
			if (sign < 0)
			{
				aWord = ~aWord;
			}
			if (value.sign < 0)
			{
				bWord = ~bWord;
			}
			resultMag[i] = aWord ^ bWord;
			if (resultNeg)
			{
				resultMag[i] = ~resultMag[i];
			}
		}
		BigInteger result = new BigInteger(1, resultMag, checkMag: true);
		if (resultNeg)
		{
			result = result.Not();
		}
		return result;
	}

	public BigInteger SetBit(int n)
	{
		if (n < 0)
		{
			throw new ArithmeticException("Bit address less than zero");
		}
		if (TestBit(n))
		{
			return this;
		}
		if (sign > 0 && n < BitLength - 1)
		{
			return FlipExistingBit(n);
		}
		return Or(One.ShiftLeft(n));
	}

	public BigInteger ClearBit(int n)
	{
		if (n < 0)
		{
			throw new ArithmeticException("Bit address less than zero");
		}
		if (!TestBit(n))
		{
			return this;
		}
		if (sign > 0 && n < BitLength - 1)
		{
			return FlipExistingBit(n);
		}
		return AndNot(One.ShiftLeft(n));
	}

	public BigInteger FlipBit(int n)
	{
		if (n < 0)
		{
			throw new ArithmeticException("Bit address less than zero");
		}
		if (sign > 0 && n < BitLength - 1)
		{
			return FlipExistingBit(n);
		}
		return Xor(One.ShiftLeft(n));
	}

	private BigInteger FlipExistingBit(int n)
	{
		Debug.Assert(sign > 0);
		Debug.Assert(n >= 0);
		Debug.Assert(n < BitLength - 1);
		int[] mag = (int[])magnitude.Clone();
		mag[mag.Length - 1 - (n >> 5)] ^= 1 << n;
		return new BigInteger(sign, mag, checkMag: false);
	}
}
